public class Leetcode {
}

//leetcode:4:寻找两个正序数组的中位数
//方法一：合并两个数组，求中间位置
// 时间复杂度O(m+n);
class Solution1 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length,m = nums2.length;
        int totalength = n+m,i=0,j=0,k=0;
        int[] arr = new int[totalength];
        while(i < n && j < m){
            if(nums1[i] <= nums2[j]){
                arr[k++] = nums1[i++];
            }else{
                arr[k++] = nums2[j++];
            }
        }
        while(i < n){
            arr[k++] = nums1[i++];
        }
        while(j < m){
            arr[k++] = nums2[j++];
        }
        return (arr[totalength/2] + arr[(totalength-1)/2])/2.0;
    }
}
//方法二：二分查找
//时间复杂度O(log(m+n));
class Solution2 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length,n = nums2.length;
        //获得两个数组的总长度
        int totalLength = m + n;
        //如果是奇数
        if(totalLength % 2 == 1){
            int mid = totalLength / 2;//找到两个数组合并后的中间位置
            //由于是奇数长度，中间位置加一得到的x，就代表合并数组中第x个数就是中位数的位置
            //合并数组这个位置的元素就是中位数结果
            double ret = get(nums1,nums2,mid+1);
            return ret;
        }else{//如果是偶数
            int mid =totalLength /2;//找到两个数组合并后中位数的位置
            //由于是偶数长度，中间位置x和中间位置加一得到的y，就代表合并数组中第x和y个数就是中位数的位置
            //合并数组这两中位数元素加在一起除2就是我们要求的中位数结果
            double ret = (get(nums1,nums2,mid) + get(nums1,nums2,mid+1))/2.0;
            return ret;
        }

    }
    //利用二分查找找第k小的数
    public int get(int[] nums1,int[] nums2,int k){
        int m = nums1.length,n = nums2.length;
        int index1 = 0,index2 = 0;
        while(true){
            //处理边界情况
            //第一个数组长度为0时，第二个数组中此时index2位置加上此时K个数就是中位数
            if(index1 == m){
                return nums2[index2+k-1];
            }
            //第二个数组长度为0时，第一个数组中此时index1位置加上此时K个数就是中位数
            if(index2 == n){
                return nums1[index1+k-1];
            }
            //如果此时k的个数为1，那么两个数组中此时index1和index2位置的元素较小的一个就是我们的中位数
            if(k == 1){
                return Math.min(nums1[index1], nums2[index2]);
            }
            //利用在两个二分查找第k小的数
            int half = k/2;
            //在两个数组分别找到k/2位置的元素（即找k/2个元素）（如果k/2超过数组长度就返回数组长度）
            //因为要找到的是k/2位置的元素所以要减去1得到数组中对应的下标
            int newindex1 = Math.min(index1+half,m)-1;
            int newindex2 = Math.min(index2+half,n)-1;
            //由于是在两个数组中分别找k/2个元素，且数组升序，如果第一个数组中newindex1位置的元素小于等于第二个数组中newindex2位置的元素
            //就让k减去此时第一个数组中index1位置到newindex1位置的元素个数，并让index1移动到newindex1的后一位
            if(nums1[newindex1] <= nums2[newindex2]){
                k -= (newindex1 - index1 + 1);
                index1 = newindex1+1;
            }else{//反之。第二个数组同理，直到k=1时，返回两个中的最小值
                k -= (newindex2 - index2 + 1);
                index2 = newindex2+1;
            }
        }
    }
}